package com.hanxiaozhang.no10leetcode.tree;

import org.apache.poi.ss.formula.functions.T;

/**
 * 〈一句话功能简述〉<br>
 * 〈把一棵二叉树展开成一个链表〉
 * <p>
 * 实例：
 * 二叉树：
 * .          1
 * .         / \
 * .        2   5
 * .       / \   \
 * .      3   4   6
 * 被压扁的树应该看起来像:
 * .    1
 * .     \
 * .      2
 * .       \
 * .        3
 * .         \
 * .          4
 * .           \
 * .            5
 * .             \
 * .              6
 * <p>
 * 题意：
 * 给一个二叉树，原址将它压成一个链表。根据例子来看：使用每个TreeNode的右孩子指针来实现这个链表。
 * 仔细观察例子，可以发现这其实就是一个先序遍历。但是，要注意每个节点的左孩子指针最后都要置为NULL；
 * 思路：
 * 知识点1：二叉树先序递归
 * 知识点2：二叉树右孩子节点链表，获取最后一个节点。
 *
 * @author hanxinghua
 * @create 2024/4/25
 * @since 1.0.0
 */
public class No114FlatternBinaryTreeToLinkedList {

    public static void main(String[] args) {

        TreeNode tree = new TreeNode(1);
        tree.left = new TreeNode(2);
        tree.right = new TreeNode(5);
        tree.left.left = new TreeNode(3);
        tree.left.right = new TreeNode(4);
        tree.right.right = new TreeNode(6);


        TreeNode treeNode = method1(tree);
        System.out.println();

    }


    /**
     * 方法1：自己的方法
     *
     * @param tree
     * @return
     */
    private static TreeNode method1(TreeNode tree) {

        if (tree == null) {
            return null;
        }

        TreeNode result = new TreeNode(-1);
        pre(tree, result);

        return result.right;
    }

    private static void pre(TreeNode root, TreeNode result) {

        if (root == null) {
            return;
        }

        addRight(result, root.val);
        pre(root.left, result);
        pre(root.right, result);
    }


    private static void addRight(TreeNode result, int val) {
        TreeNode lastNode = result;
        while (lastNode.right != null) {
            lastNode = lastNode.right;
        }
        lastNode.right = new TreeNode(val);
    }

}
